package com.base.dataStructure.recurrence;

import java.util.Arrays;

/**
 * @Author: hdhao
 * @Create: 2023/3/28 - 21:40
 * @Version: v1.0
 */
//递归实现插入排序
public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {8,1,3,2,5,9,10};
        System.out.println(Arrays.toString(a));
        insertion(a,1);
        System.out.println(Arrays.toString(a));
    }
    /**
     * 插入排序实现
     * @param a 待排序数组
     * @param low 未排序区域左边界索引
     *  插入排序将数组分为两个部分(已排序区域和未排序区域),默认情况下
     *  认为第一个元素为已排序区域,后续区域是未排序的
     */
    public static void insertion(int[] a,int low){
        //当未排序区域的左边界=a的长度时,代表已经排序完成
        if (low == a.length){
            return;
        }
        //未排序区域最左边的值
        int temp = a[low];
        //已排序区域最右边的索引
        int i = low-1;
        //当已排序区域最右边的值比未排序区域最左边的值还大,就一直循环
        while (i >= 0 && a[i] > temp){
            //将已排序区域最右边的值向右移动,空出来插入的位置
            a[i+1] = a[i];
            i--;
        }
        //当退出循环,说明找到了插入位置
        a[i+1] = temp;

        //随着排序过程的推进,未排序区域的左边界不断的向右推进
        insertion(a,low+1);
    }
}
